﻿/*
Digraph (library for building, traversal, comparison and saving of directed
graph).

Copyright (C) 2014 Dmitry Merzagitovich Arslanov

This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 2.1 of the License, or (at your option) any
later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
*/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.ComponentModel;
using System.IO;
using System.Linq;
using System.Text;

namespace Digraph
{
    /// <summary>
    /// Directed graph is a set of elements and their ordered pairs called
    /// vertices and arcs accordingly. Arc represents connected vertices.
    /// Digraph may contain not connected vertices, loops, multiple arcs
    /// between two vertices and not connected sub digraphs.
    /// </summary>
    /// <typeparam name="TVertex">Type of digraph vertex content.</typeparam>
    /// <typeparam name="TArc">Type of digraph arc content.</typeparam>
    public sealed class Set<TVertex, TArc>
    {
        internal List<Vertex<TVertex, TArc>> VertexList;

        /// <summary>
        /// Elements of digraph.
        /// </summary>
        public ReadOnlyCollection<Vertex<TVertex, TArc>> Vertices
        {
            get
            {
                return VertexList.AsReadOnly();
            }
        }

        internal List<Arc<TVertex, TArc>> ArcList;

        /// <summary>
        /// Ordered pairs of some digraph vertices represent connection between
        /// two vertices.
        /// </summary>
        public ReadOnlyCollection<Arc<TVertex, TArc>> Arcs
        {
            get
            {
                return ArcList.AsReadOnly();
            }
        }

        internal Set()
        {
            VertexList = new List<Vertex<TVertex, TArc>>();
            ArcList = new List<Arc<TVertex, TArc>>();
        }

        /// <summary>
        /// Get difference between initial and result digraph.
        /// </summary>
        /// <param name="initialDigraph">Digraph before changes.</param>
        /// <param name="resultDigraph">Digraph after changes.</param>
        /// <returns>
        /// Changes which need to be made to receive a result digraph from
        /// an initial digraph.
        /// </returns>
        public static Difference<TVertex, TArc> Compare(
            Set<TVertex, TArc> initialDigraph,
            Set<TVertex, TArc> resultDigraph)
        {
            Difference<TVertex, TArc> difference =
                new Difference<TVertex, TArc>();
            foreach (Vertex<TVertex, TArc> resV in resultDigraph.VertexList)
            {
                if (!initialDigraph.VertexList.Contains(resV))
                {
                    difference.AddedVertexList.Add(resV);
                }
            }
            foreach (Arc<TVertex, TArc> resultArc in resultDigraph.ArcList)
            {
                if (!initialDigraph.ArcList.Contains(resultArc))
                {
                    difference.AddedArcList.Add(resultArc);
                }
            }
            foreach (Vertex<TVertex, TArc> iniV in initialDigraph.VertexList)
            {
                if (!resultDigraph.VertexList.Contains(iniV))
                    difference.RemovedVertexList.Add(iniV);
            }
            foreach (Arc<TVertex, TArc> initialArc in initialDigraph.ArcList)
            {
                if (!resultDigraph.ArcList.Contains(initialArc))
                    difference.RemovedArcList.Add(initialArc);
            }
            return difference;
        }

        /// <summary>
        /// Searches for a vertex that matches the conditions defined by the
        /// specified predicate, and returns the first occurrence within the
        /// entire digraph.
        /// </summary>
        /// <param name="match">
        /// The delegate that defines the conditions of the vertex to search
        /// for.
        /// </param>
        /// <returns>
        /// The first vertex that matches the conditions defined by the
        /// specified predicate, if found; otherwise, null.
        /// </returns>
        public Vertex<TVertex, TArc> GetVertex(
            Predicate<Vertex<TVertex, TArc>> match)
        {
            return VertexList.Find(match);
        }

        /// <summary>
        /// Retrieves all the vertices that match the conditions defined by
        /// the specified predicate.
        /// </summary>
        /// <param name="match">
        /// The delegate that defines the conditions of the vertices to search
        /// for.
        /// </param>
        /// <returns>
        /// A list containing all the vertices that match the conditions
        /// defined by the specified predicate, if found; otherwise, an empty
        /// list.
        /// </returns>
        public List<Vertex<TVertex, TArc>> GetVertices(
            Predicate<Vertex<TVertex, TArc>> match)
        {
            return VertexList.FindAll(match);
        }

        /// <summary>
        /// Searches for an arc that matches the conditions defined by the
        /// specified predicate, and returns the first occurrence within the
        /// entire digraph.
        /// </summary>
        /// <param name="match">
        /// The delegate that defines the conditions of the arc to search for.
        /// </param>
        /// <returns>
        /// The first arc that matches the conditions defined by the specified
        /// predicate, if found; otherwise, null.
        /// </returns>
        public Arc<TVertex, TArc> GetArc(Predicate<Arc<TVertex, TArc>> match)
        {
            return ArcList.Find(match);
        }

        /// <summary>
        /// Retrieves all the arcs that match the conditions defined by
        /// the specified predicate.
        /// </summary>
        /// <param name="match">
        /// The delegate that defines the conditions of the arcs to search for.
        /// </param>
        /// <returns>
        /// A list containing all the arcs that match the conditions defined by
        /// the specified predicate, if found; otherwise, an empty list.
        /// </returns>
        public List<Arc<TVertex, TArc>> GetArcs(
            Predicate<Arc<TVertex, TArc>> match)
        {
            return ArcList.FindAll(match);
        }

        /// <summary>
        /// Get digraph vertices with outcoming arcs but without incoming arcs.
        /// </summary>
        /// <returns>
        /// Vertices with outcoming arcs but without incoming arcs.
        /// </returns>
        public List<Vertex<TVertex, TArc>> GetSources()
        {
            return VertexList.FindAll(vertex => vertex.IsSource);
        }

        /// <summary>
        /// Get digraph vertices with incoming arcs but without outcoming arcs.
        /// </summary>
        /// <returns>
        /// Vertices with incoming arcs but without outcoming arcs.
        /// </returns>
        public List<Vertex<TVertex, TArc>> GetSinks()
        {
            return VertexList.FindAll(vertex => vertex.IsSink);
        }

        /// <summary>
        /// Get digraph vertices with incoming and outcoming arcs.
        /// </summary>
        /// <returns>Vertices with incoming and outcoming arcs.</returns>
        public List<Vertex<TVertex, TArc>> GetIsolatedVertices()
        {
            return VertexList.FindAll(vertex => vertex.IsIsolated);
        }

        /// <summary>
        /// Get all pathes in digraph.
        /// </summary>
        /// <returns>List of pathes. Path is list of arcs.</returns>
        public List<Path<TVertex, TArc>> GetPathes()
        {
            List<Path<TVertex, TArc>> pathes = new List<Path<TVertex, TArc>>();
            Trace<TVertex, TArc> trace = new Trace<TVertex, TArc>();
            List<Vertex<TVertex, TArc>> sourceVertices = GetSources();
            Stack<Path<TVertex, TArc>> tracedPathes =
                new Stack<Path<TVertex, TArc>>();
            foreach (Vertex<TVertex, TArc> srcV in sourceVertices)
            {
                foreach (Arc<TVertex, TArc> arc in srcV.OutcomingArcList)
                {
                    Path<TVertex, TArc> path = new Path<TVertex, TArc>();
                    path.Add(arc);
                    tracedPathes.Push(path);
                }
            }
            while (tracedPathes.Count > 0)
            {
                Path<TVertex, TArc> tracedPath = tracedPathes.Pop();
                pathes.Add(tracedPath);
                Arc<TVertex, TArc> pos = tracedPath.Last();
                while (pos != null)
                {
                    Arc<TVertex, TArc> nextPosition = null;
                    List<Arc<TVertex, TArc>> arcs =
                        pos.ToVertex.OutcomingArcList;
                    foreach (Arc<TVertex, TArc> arc in arcs)
                    {
                        Step<TVertex, TArc> step =
                            new Step<TVertex, TArc>(pos, arc);
                        if (!trace.Contains(step))
                        {
                            if (nextPosition == null)
                            {
                                trace.Add(step);
                                nextPosition = arc;
                            }
                            else
                            {
                                tracedPathes.Push(
                                    new Path<TVertex, TArc>(tracedPath));
                            }
                        }
                    }
                    if (nextPosition != null) tracedPath.Add(nextPosition);
                    pos = nextPosition;
                }
            }
            return pathes;
        }

        /// <summary>
        /// Get minimum path between two vertices.
        /// </summary>
        /// <param name="fromVertex">Begin vertex of path.</param>
        /// <param name="toVertex">End vertex of path.</param>
        /// <param name="arcLengthCalculator">
        /// User supplied delegate for calculation of digraph arc length.
        /// </param>
        /// <returns>
        /// Minimum path between two vertices or null if vertives are not
        /// connected.
        /// </returns>
        public Path<TVertex, TArc> GetMinimumPath(
            Vertex<TVertex, TArc> fromVertex,
            Vertex<TVertex, TArc> toVertex,
            ArcLengthCalculator<TVertex, TArc> arcLengthCalculator)
        {
            if (arcLengthCalculator == null) throw new ArgumentNullException();
            List<Path<TVertex, TArc>> allPathes = GetPathes();
            Path<TVertex, TArc> minPath = null;
            double minLen = double.MaxValue;
            foreach (Path<TVertex, TArc> path in allPathes)
            {
                Path<TVertex, TArc> subPath = path.GetSubPath(fromVertex,
                                                              toVertex);
                if (subPath != null)
                {
                    double length = subPath.CalcLength(arcLengthCalculator);
                    if (length < minLen)
                    {
                        minLen = length;
                        minPath = path;
                    }
                }
            }
            return minPath;
        }

        /// <summary>
        /// Enumerate all vertices in digraph.
        /// </summary>
        /// <param name="startFromSink">
        /// True if enumeration is started from sink vertices. 
        /// False if enumeration is started from source vertices.
        /// </param>
        /// <param name="enumerateInWidth">
        /// True if for current vertex all adjacent vertices are enumerated at
        /// first. False if vertices are enumerated through first appeared arc.
        /// </param>
        /// <param name="vertexCallback">
        /// User supplied callback function for digraph vertex processing
        /// during enumeration.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// This exception is thrown if enumerationCallback is null.
        /// </exception>
        public void ForEachVertex(bool startFromSink,
            bool enumerateInWidth,
            VertexCallback<TVertex, TArc> vertexCallback)
        {
            if (vertexCallback == null) throw new ArgumentNullException();
            List<Vertex<TVertex, TArc>> enumeratedVertices =
                new List<Vertex<TVertex, TArc>>();
            List<Vertex<TVertex, TArc>> vertices = GetIsolatedVertices();
            vertices.AddRange(startFromSink ? GetSinks() : GetSources());
            while (vertices.Count > 0)
            {
                Vertex<TVertex, TArc> vertex = vertices[0];
                vertices.RemoveAt(0);
                vertexCallback(vertex);
                enumeratedVertices.Add(vertex);
                List<Arc<TVertex, TArc>> arcs = startFromSink ?
                    vertex.IncomingArcList : vertex.OutcomingArcList;
                int i = 0;
                foreach (Arc<TVertex, TArc> arc in arcs)
                {
                    Vertex<TVertex, TArc> nextVertex = startFromSink ?
                        arc.FromVertex : arc.ToVertex;
                    if (!enumeratedVertices.Contains(nextVertex) &&
                        !vertices.Contains(nextVertex))
                    {
                        if (enumerateInWidth) vertices.Add(nextVertex);
                        else
                        {
                            if (i == vertices.Count)
                                vertices.Add(nextVertex);
                            else
                                vertices.Insert(i, nextVertex);
                            i++;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Traverse vertices in digraph.
        /// </summary>
        /// <param name="fromVertex">Starting vertex of traversal.</param>
        /// <param name="direction">
        /// Indicates which vertices are selected for traversal from current
        /// position in digraph.
        /// </param>
        /// <param name="vertexSelector">
        /// User supplied callback function to select vertex for next step of
        /// digraph traverse.
        /// </param>
        /// <param name="vertexCallback">
        /// User supplied callback function for digraph vertex processing
        /// during traversal.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// This exception is thrown if traversedVertexSelector and
        /// traverseCallback are null.
        /// </exception>
        public void Traverse(Vertex<TVertex, TArc> fromVertex,
                             Direction direction,
                             VertexSelector<TVertex, TArc> vertexSelector,
                             VertexCallback<TVertex, TArc> vertexCallback)
        {
            if (vertexSelector == null || vertexCallback == null)
                throw new ArgumentNullException();
            Vertex<TVertex, TArc> curV = fromVertex;
            while (curV != null)
            {
                List<Vertex<TVertex, TArc>> vertices =
                    new List<Vertex<TVertex, TArc>>();
                if (direction == Direction.Forward ||
                    direction == Direction.Both)
                {
                    foreach (Arc<TVertex, TArc> arc in curV.OutcomingArcList)
                    {
                        vertices.Add(arc.ToVertex);
                    }
                }
                if (direction == Direction.Backward ||
                    direction == Direction.Both)
                {
                    foreach (Arc<TVertex, TArc> arc in curV.IncomingArcList)
                    {
                        vertices.Add(arc.FromVertex);
                    }
                }
                curV = null;
                foreach (Vertex<TVertex, TArc> vertex in vertices)
                {
                    curV = vertexSelector(curV, vertex);
                }
                vertexCallback(curV);
            }
        }

        /// <summary>
        /// Returns a string that represents the current digraph in trivial
        /// graph format (TGF).
        /// <para>Tgf sample:</para>
        /// <para>1 Content of first vertex</para>
        /// <para>2 Content of second vertex</para>
        /// <para>#</para>
        /// <para>1 2 Content of arc between first and second vertices</para>
        /// Provide <see cref="System.ComponentModel.TypeConverter" /> to save
        /// vertex and arc contents in strings.
        /// </summary>
        /// <returns>
        /// String that represents the current digraph in tgf.
        /// </returns>
        /// <exception cref="CantConvertVertexToStringException">
        /// This exception is thrown if
        /// <see cref="System.ComponentModel.TypeConverter" /> is not specified
        /// for vertex content type which provides vertex to string conversion.
        /// </exception>
        /// <exception cref="CantConvertArcToStringException">
        /// This exception is thrown if
        /// <see cref="System.ComponentModel.TypeConverter" /> is not specified
        /// for arc content type which provides arc to string conversion.
        /// </exception>
        public override string ToString()
        {
            Type stringType = typeof(string);
            TypeConverter vtxConv = TypeDescriptor.GetConverter(
                typeof(TVertex));
            if (!vtxConv.CanConvertTo(stringType))
                throw new CantConvertVertexToStringException();
            TypeConverter arcConv = TypeDescriptor.GetConverter(
                typeof(TArc));
            if (!arcConv.CanConvertTo(stringType))
                throw new CantConvertArcToStringException();
            StringWriter writer = new StringWriter();
            for (int i = 0; i < VertexList.Count; i++)
            {
                TVertex cnt = VertexList[i].Content;
                if (EqualityComparer<TVertex>.Default.Equals(cnt,
                                                             default(TVertex)))
                {
                    writer.WriteLine(i + 1);
                }
                else
                {
                    string cStr = vtxConv.ConvertTo(cnt, stringType) as string;
                    writer.WriteLine("{0} {1}", i + 1, cStr);
                }
            }
            writer.WriteLine("#");
            foreach (Arc<TVertex, TArc> arc in ArcList)
            {
                int i = VertexList.IndexOf(arc.FromVertex) + 1;
                int j = VertexList.IndexOf(arc.ToVertex) + 1;
                string aStr = arcConv.ConvertTo(arc.Content,
                    stringType) as string;
                writer.WriteLine("{0} {1} {2}", i, j, aStr);
            }
            writer.Flush();
            return writer.ToString();
        }

        /// <summary>
        /// Save digraph in tgf stream with specified encoding:
        /// <para>1 Content of first vertex</para>
        /// <para>2 Content of second vertex</para>
        /// <para>#</para>
        /// <para>1 2 Content of arc between first and second vertices</para>
        /// Provide <see cref="System.ComponentModel.TypeConverter" /> to save
        /// vertex and arc contents in strings.
        /// </summary>
        /// <param name="stream">Stream where digraph is saved.</param>
        /// <param name="encoding">Stream encoding.</param>
        public void Save(Stream stream, Encoding encoding)
        {
            StreamWriter writer = new StreamWriter(stream, encoding);
            writer.Write(ToString());
            writer.Flush();
        }

        /// <summary>
        /// Save digraph in tgf stream with default encoding:
        /// <para>1 Content of first vertex</para>
        /// <para>2 Content of second vertex</para>
        /// <para>#</para>
        /// <para>1 2 Content of arc between first and second vertices</para>
        /// Provide <see cref="System.ComponentModel.TypeConverter" /> to save
        /// vertex and arc contents in strings.
        /// </summary>
        /// <param name="stream">Stream where digraph is saved.</param>
        public void Save(Stream stream)
        {
            Save(stream, Encoding.Default);
        }

        /// <summary>
        /// Save digraph in tgf file with specified encoding:
        /// <para>1 Content of first vertex</para>
        /// <para>2 Content of second vertex</para>
        /// <para>#</para>
        /// <para>1 2 Content of arc between first and second vertices</para>
        /// Provide <see cref="System.ComponentModel.TypeConverter" /> to save
        /// vertex and arc contents in strings.
        /// </summary>
        /// <param name="fileName">Tgf file name.</param>
        /// <param name="encoding">File encoding.</param>
        public void Save(string fileName, Encoding encoding)
        {
            using (FileStream file = File.Create(fileName))
            {
                Save(file, encoding);
            }
        }

        /// <summary>
        /// Save digraph in tgf file with default encoding:
        /// <para>1 Content of first vertex</para>
        /// <para>2 Content of second vertex</para>
        /// <para>#</para>
        /// <para>1 2 Content of arc between first and second vertices</para>
        /// Provide <see cref="System.ComponentModel.TypeConverter" /> to save
        /// vertex and arc contents in strings.
        /// </summary>
        /// <param name="fileName">Tgf file name.</param>
        public void Save(string fileName)
        {
            Save(fileName, Encoding.Default);
        }
    }
}
